package zuochengyun;

import java.util.HashMap;

public class GetPosArray {

	public static void main(String[] args) {
		GetPosArray obArray = new GetPosArray();
		int[] pre = {1, 2, 4, 5, 3, 6, 7, 9, 8};
		int[] in = {2, 4, 5, 1, 6, 3, 9, 8, 7};
		int[] pos = obArray.getPosArray(pre, in);
		for (int i = 0; i < pos.length; i++) {
			System.out.print(pos[i] + "  ");
		}
	}
	/**
	 * 通过前序和中序直接获取后序数组
	 */
	public int[] getPosArray(int[] pre, int[] in){
		if(pre == null || in == null){
			return null;
		}
		int length = pre.length;
		int[] pos = new int[length];
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i = 0; i < length; i++){
			map.put(in[i], i);
		}
		setPos2(pre, 0, 0, length - 1, in, 0, length - 1, pos, length - 1, map);
		return pos;
	}
	
	/**
	 * 
	 * @param pre
	 * @param rootPosition  此时根节点的下标
	 * @param length
	 * @param in
	 * @param rightStart
	 * @param rightEnd
	 * @param pos
	 * @param position 表示的是后序数组应该填充的下标，从右往左开始
	 * @param map
	 * @return pos该填的下一个下一个位置的下标
	 */
	public int setPos(int[] pre, int rootPosition, int length, int[] in, int rightStart, int rightEnd,
			int[] pos, int position, HashMap<Integer, Integer> map){
		if(rootPosition > length){
			return position;
		}
		for (int j = 0; j < pos.length; j++) {
			System.out.print(pos[j] + "  ");
		}
		System.out.println("----------");
		//pre[rootPosition]表示的是根节点
		pos[position--] = pre[rootPosition];
		int i = map.get(pre[rootPosition]);
		//先设置右子树
		System.out.println("tsetCase : " + length + "  " + rightEnd);
		position = setPos(pre, rootPosition + 1 + (rightEnd - i), length, in, i + 1, rightEnd, pos, position, map);
		for (int j = 0; j < pos.length; j++) {
			System.out.print(pos[j] + "  ");
		}
		System.out.println("-----");
		return setPos(pre, rootPosition + 1, rootPosition + i - rightStart, in, rightStart, i - 1, pos, position, map);
	}
	
	public int setPos2(int[] pre, int rootPosition, int preStart, int preEnd, int[] in, int inStart,
			int inEnd, int[] pos, int position, HashMap<Integer, Integer> map){
		if(preStart > preEnd){
			return position;
		}
		if(inStart > inEnd){
			return position;
		}
		System.out.println("rootposition：" + rootPosition);
		System.out.println("start:" + preStart + " " + preEnd + " " + inStart + " " + inEnd);
		for (int j = 0; j < pos.length; j++) {
			System.out.print(pos[j] + "  ");
		}
		System.out.println("----------");
		//pre[rootPosition]表示的是根节点
		pos[position--] = pre[rootPosition];
		int i = map.get(pre[rootPosition]);
		//先设置右子树
		//注意，比如 前序序列为 7 9 8， 中序序列为 9 8 7 
		//那么会出现preStart和inStart不一致的情况，所以要加一个preStart - endStart
		
		position = setPos2(pre, i + 1 + (preStart - inStart), i + 1 + (preStart - inStart)
				, preEnd, in, i + 1, inEnd, pos, position, map);
		for (int j = 0; j < pos.length; j++) {
			System.out.print(pos[j] + "  ");
		}
		System.out.println("-----");
		return setPos2(pre, rootPosition + 1, rootPosition + 1, i, in, inStart, i - 1, pos, position, map);
	}
}
